1. Field of the Invention
Embodiments of the present invention generally relate to routing in a packet network and, more particularly, to a method and apparatus for mitigating routing misbehavior in a network.
2. Description of the Related Art
The Internet originated from a research network where both end hosts, as well as network components such as routers and switches, are assumed to be well behaved or cooperative. The original Internet design philosophy addresses physical failures well; however, it fails to address problems resulting from misbehaving or non-cooperative end users, network components and misconfigurations. Routers inside the network can misbehave due to misconfigurations or malicious attackers. Today, the Internet has no robust defense mechanisms against misbehaving routers, leaving the Internet routing infrastructure largely unprotected.
As used herein, the control plane is defined as the Internet routing layer, and the data plane is defined as the packet forwarding layer. In the control plane, routing updates are exchanged among routers using a routing protocol. Routers within a domain typically use an interior gateway protocol (IGP), such as open shortest path first (OSPF), to exchange routing updates. Routing updates are exchanged between domains using an exterior gateway protocol (EGP), such as the border gateway protocol (BGP).
BGP is the inter-domain routing protocol that autonomous systems use to exchange information about how to reach destination address blocks or prefixes. Each AS is a network entity with well-defined routing policies. BGP sessions between routers within the same AS are Internal BGP (iBGP) sessions and can traverse through several Internet Protocol (IP) hops. BGP sessions between routers belonging to different AS are External BGP (eBGP) sessions and usually are established over a single hop to ensure low latency and loss rate.
There are four types of BGP messages within BGP traffic: OPEN, KEEPALIVE, NOTIFICATION and UPDATE. The OPEN message is used to establish the BGP session between two routers. Once the session is established, BGP neighbors send each other periodic KEEPALIVE messages to confirm the liveness of the connection. If an error occurs during the life time of a BGP session, a NOTIFICATION message is sent to signal the presence of such error before the underlying TCP connection is closed. The UPDATE message is the primary message used to communicate information between BGP routers. There are two types of BGP UPDATE messages: announcements and withdrawals. Announcements indicate the availability of a new route to a destination IP prefix. Withdrawals indicate that the sender no longer has a route to the destination.
BGP is a path vector protocol, as the AS_PATH attribute contains the sequence of autonomous systems of the route. Each BGP UPDATE message contains other path attributes such as NEXT_HOP, ORIGIN, MED (Multiple-Exit-Discriminator), COMMUNITY, ATOMIC_AGGREGATE and AGGREGATOR. All such attributes can influence the route selection decision. Some of the attributes such as ORIGIN, AS_PATH, and NEXT_HOP are mandatory. By representing the path at the AS level, BGP hides the details of the topology and routing inside each network. BGP is also incremental, i.e. every BGP UPDATE message indicates a routing change. In addition, BGP is policy-oriented. Rather than selecting the route with the shortest AS path, routers can apply complex policies to influence the selection of the best route for each prefix and to decide whether to propagate this route to neighbors.
There is an inherent trust relationship in the routing system: a router always trusts the routing updates advertised by its neighboring routers. A router assumes that the routing information in the updates is accurate, i.e., usable for forwarding traffic that will follow the corresponding path information in the update. However, router misconfigurations, routing attacks, and inherent routing problems, such as deflection, often render this assumption incorrect. Accordingly, there exists a need in the art for a method and apparatus for mitigating routing misbehavior in a network.